%short introduction to the problem and a description of the relationship to the course material. also present what ytou think are your biggest contributions so that this is clear. be sure to credit anyone that you got help/code from
\section{Introduction}
The human species is unlike any other species because of our ability to make logical, intelligent decisions. We use our current knowledge and past experiences to predict the best future action. Our brains are able to make these complex decisions in an instant. Scientists have been trying to mimic humanistic intelligent decision-making for many years. Despite their efforts, there is no perfect replica of the human brain. However, studies of artificial intelligence continue to flourish in many different areas, including solving puzzles such as Sokoban. This is the problem that we set out to solve. Although no one has found a perfect solution to Sokoban, with the help of the teacher assistants and other online resources we set out to create a decent Sokoban puzzle solver of our own.

The goal of Sokoban is to have the player move each box onto a goal. The player is only allowed to push the boxes, no pulling. The main challenge of Sokoban is figuring out how to solve the puzzle in a reasonable amount of time. If we had unlimited processing power, time and memory, we could find a solution by trying every possible combination of box to goal paths. But since we don’t have these unlimited resources; our challenge is to solve each puzzle board in less than one minute. In order to do this we must use a clever algorithm and implement different techniques to minimize our solution space into a reasonably sized set to analyze.  In addition the broad sizes and configurations vary greatly, including the number of goals and boxes and their positions. It is often the case that boxes must be solved in a specific order, and figuring out that order is no simple task.

Our first approach to solving Sokoban was to implement a breadth-first search based algorithm. After several iterations we finally settled on using the A* algorithm to find the paths from boxes to goals. After having defined the main approach to solve the problem we realized that, as in the Othello project, pruning the search tree was very important. So we included several different methods of pruning invalid solutions.

One method of pruning was to check for deadlock positions. Because boxes can only be pushed and not pulled, if a box is moved into one of these deadlock positions then the board immediately becomes unsolvable. If it’s a deadlock then we can just skip checking this solution any further because we know it will lead to an unsolvable board.

The other pruning method implied not looking for boards that were 'similar' to other boards that we had already tested.